👀 Reading hidden code

130 μs

👀 Reading hidden code

14.5 μs

Welcome to 18.S191 – Fall 2020!

Introduction to Computational Thinking for Real-World Problems

👀 Reading hidden code

41.5 ms

👀 Reading hidden code

12.6 μs

https://github.com/mitmath/18S191

👀 Reading hidden code

58.9 ms

👀 Reading hidden code

13.8 μs

Alan Edelman, David P. Sanders, Grant Sanderson, James Schloss

👀 Reading hidden code

5.3 ms

& Philip the Corgi

👀 Reading hidden code

201 μs

Class outline

Data and computation

Module 1: Analyzing images
Module 2: Particles and ray tracing
Module 3: Epidemic spread
Module 4: Climate change

👀 Reading hidden code

9.4 ms

Tools

Julia programming language: http://www.julialang.org/learning
Pluto notebook environment

👀 Reading hidden code

5.3 ms

Module 1: Images

👀 Reading hidden code

198 μs

4 + 4

👀 Reading hidden code

12.2 μs

Data takes many forms

Time series:
- Number of infections per day
- Stock price each minute
- A piece for violin broadcast over the radio

Video:
- The view from a window of a self-driving car
- A hurricane monitoring station

Images:
- Diseased versus healthy tissue in a scan
- Deep space via the Hubble telescope
- Can your social media account recognise your friends?

👀 Reading hidden code

7.2 ms

Capture your own image!

👀 Reading hidden code

188 μs

👀 Reading hidden code

67.3 μs

Enable webcam

@bind raw_camera_data camera_input(;max_size=2000)

👀 Reading hidden code

46.1 ms

👀 Reading hidden code

174 μs

Error message

Another cell defining grant contains errors.

[

grant grant[:,end:-1:1]

grant[end:-1:1,:] grant[end:-1:1,end:-1:1]

]

👀 Reading hidden code

---

Error message

MethodError: no method matching getindex(::Missing, ::String)

Stack trace

Here is what happened, the most recent locations are first:

process_raw_camera_data

(raw_camera_data::Missing)

from Other cell: line 13

	# So to get the red values for each pixel, we take every 4th value, starting at 	# the 1st:	reds_flat = UInt8.(raw_camera_data["data"][1:4:end])	greens_flat = UInt8.(raw_camera_data["data"][2:4:end])	blues_flat = UInt8.(raw_camera_data["data"][3:4:end])

Show more...

grant = decimate(process_raw_camera_data(raw_camera_data), 2)

👀 Reading hidden code

---

What is an image?

👀 Reading hidden code

177 μs

Albrecht Dürer:

👀 Reading hidden code

199 μs

👀 Reading hidden code

1.9 ms

An image is:

A 2D representation of a 3D world
An approximation

👀 Reading hidden code

447 μs

What is an image, though?

A grid of coloured squares called pixels
A colour for each pair $(i, j)$ of indices
A discretization

👀 Reading hidden code

5.7 ms

How can we store an image in the computer?

Is it a 1D array (Vector)?
A 2D array (Matrix)?
A 3D array (tensor)?

👀 Reading hidden code

518 μs

If in doubt: Ask Julia!

Let's use the Images.jl package to load an image and see what we get

👀 Reading hidden code

385 μs

begin

import Pkg

Pkg.activate(mktempdir())

end

👀 Reading hidden code

  Activating new project at `/tmp/jl_4mrqNz`

132 ms

begin

Pkg.add(["Images", "ImageIO", "ImageMagick"])

using Images

end

👀 Reading hidden code

    Updating registry at `~/.julia/registries/General.toml`
   Resolving package versions...
    Updating `/tmp/jl_4mrqNz/Project.toml`
  [82e4d734] + ImageIO v0.6.9
  [6218d12a] + ImageMagick v1.4.0
  [916415d5] + Images v0.26.2
    Updating `/tmp/jl_4mrqNz/Manifest.toml`
  [621f4979] + AbstractFFTs v1.5.0
  [79e6a3ab] + Adapt v3.7.2
  [66dad0bd] + AliasTables v1.1.3
  [ec485272] + ArnoldiMethod v0.4.0
  [4fba245c] + ArrayInterface v7.5.1
  [13072b0f] + AxisAlgorithms v1.1.0
  [39de3d68] + AxisArrays v0.4.7
  [62783981] + BitTwiddlingConvenienceFunctions v0.1.6
  [fa961155] + CEnum v0.5.0
  [2a0fbf3d] + CPUSummary v0.2.6
  [aafaddc9] + CatIndices v0.2.2
  [d360d2e6] + ChainRulesCore v1.25.1
  [9e997f8a] + ChangesOfVariables v0.1.9
  [fb6a15b2] + CloseOpenIntervals v0.1.13
  [aaaa29a8] + Clustering v0.15.8
  [35d6a980] + ColorSchemes v3.29.0
  [3da002f7] + ColorTypes v0.12.0
  [c3611d14] + ColorVectorSpace v0.11.0
  [5ae59095] + Colors v0.13.0
  [bbf7d656] + CommonSubexpressions v0.3.1
  [34da2185] + Compat v4.16.0
  [ed09eef8] + ComputationalResources v0.3.2
  [187b0558] + ConstructionBase v1.5.8
  [150eb455] + CoordinateTransformations v0.6.3
  [adafc99b] + CpuId v0.3.1
  [dc8bdbbb] + CustomUnitRanges v1.0.2
  [9a962f9c] + DataAPI v1.16.0
  [864edb3b] + DataStructures v0.18.20
  [163ba53b] + DiffResults v1.1.0
  [b552c78f] + DiffRules v1.15.1
  [b4f34e82] + Distances v0.10.12
  [ffbed154] + DocStringExtensions v0.9.3
  [4f61f5a4] + FFTViews v0.3.2
  [7a1cc6ca] + FFTW v1.8.1
  [5789e2e9] + FileIO v1.17.0
  [53c48c17] + FixedPointNumbers v0.8.5
  [f6369f11] + ForwardDiff v0.10.38
  [a2bd30eb] + Graphics v1.1.3
  [86223c79] + Graphs v1.12.0
  [2c695a8d] + HistogramThresholding v0.3.1
  [3e5b6fbb] + HostCPUFeatures v0.1.17
  [615f187c] + IfElse v0.1.1
  [2803e5a7] + ImageAxes v0.6.12
  [c817782e] + ImageBase v0.1.7
  [cbc4b850] + ImageBinarization v0.3.1
  [f332f351] + ImageContrastAdjustment v0.3.12
  [a09fc81d] + ImageCore v0.10.5
  [89d5987c] + ImageCorners v0.1.3
  [51556ac3] + ImageDistances v0.2.17
  [6a3955dd] + ImageFiltering v0.7.9
  [82e4d734] + ImageIO v0.6.9
  [6218d12a] + ImageMagick v1.4.0
  [bc367c6b] + ImageMetadata v0.9.10
  [787d08f9] + ImageMorphology v0.4.5
  [2996bd0c] + ImageQualityIndexes v0.3.7
  [80713f31] + ImageSegmentation v1.8.4
  [4e3cecfd] + ImageShow v0.3.8
  [02fcd773] + ImageTransformations v0.10.1
  [916415d5] + Images v0.26.2
  [9b13fd28] + IndirectArrays v1.0.0
  [d25df0c9] + Inflate v0.1.5
  [1d092043] + IntegralArrays v0.1.6
  [a98d9a8b] + Interpolations v0.15.1
  [8197267c] + IntervalSets v0.7.10
  [3587e190] + InverseFunctions v0.1.17
  [92d709cd] + IrrationalConstants v0.2.4
  [c8e1da08] + IterTools v1.4.0
  [033835bb] + JLD2 v0.5.11
  [692b3bcd] + JLLWrappers v1.7.0
  [b835a17e] + JpegTurbo v0.1.5
  [10f19ff3] + LayoutPointers v0.1.17
  [8cdb02fc] + LazyModules v0.3.1
  [2ab3a3ac] + LogExpFunctions v0.3.28
  [bdcacae8] + LoopVectorization v0.12.171
  [1914dd2f] + MacroTools v0.5.15
  [d125e4d3] + ManualMemory v0.1.8
  [dbb5928d] + MappedArrays v0.4.2
  [626554b9] + MetaGraphs v0.8.0
  [e1d29d7a] + Missings v1.2.0
  [e94cdb99] + MosaicViews v0.3.4
  [77ba4419] + NaNMath v1.0.3
  [b8a86587] + NearestNeighbors v0.4.21
  [f09324ee] + Netpbm v1.1.1
  [6fe1bfb0] + OffsetArrays v1.15.0
  [52e1d378] + OpenEXR v0.3.3
  [bac558e1] + OrderedCollections v1.8.0
  [f57f5aa1] + PNGFiles v0.4.4
  [5432bcbf] + PaddedViews v0.5.12
  [d96e819e] + Parameters v0.12.3
  [eebad327] + PkgVersion v0.3.3
  [1d0040c9] + PolyesterWeave v0.2.2
  [f27b6e38] + Polynomials v4.0.19
  [aea7be01] + PrecompileTools v1.2.1
  [21216c6a] + Preferences v1.4.3
  [92933f4c] + ProgressMeter v1.10.2
  [43287f4e] + PtrArrays v1.3.0
  [4b34888f] + QOI v1.0.1
  [94ee1d12] + Quaternions v0.7.6
  [b3c3ace0] + RangeArrays v0.3.2
  [c84ed2f1] + Ratios v0.4.5
  [c1ae055f] + RealDot v0.1.0
  [3cdcf5f2] + RecipesBase v1.3.4
  [189a3867] + Reexport v1.2.2
  [dee08c22] + RegionTrees v0.3.2
  [ae029012] + Requires v1.3.1
  [6038ab10] + Rotations v1.7.1
  [fdea26ae] + SIMD v3.7.1
  [94e857df] + SIMDTypes v0.1.0
  [476501e8] + SLEEFPirates v0.6.43
  [efcf1570] + Setfield v1.1.2
  [699a6c99] + SimpleTraits v0.9.4
  [47aef6b3] + SimpleWeightedGraphs v1.4.0
  [45858cf5] + Sixel v0.1.3
  [a2af1166] + SortingAlgorithms v1.2.1
  [276daf66] + SpecialFunctions v2.5.0
  [cae243ae] + StackViews v0.1.1
  [aedffcd0] + Static v0.8.9
  [0d7ed370] + StaticArrayInterface v1.6.0
  [90137ffa] + StaticArrays v1.9.13
  [1e83bf80] + StaticArraysCore v1.4.3
  [82ae8749] + StatsAPI v1.7.0
  [2913bbd2] + StatsBase v0.34.4
  [62fd8b95] + TensorCore v0.1.1
  [8290d209] + ThreadingUtilities v0.5.2
  [731e570b] + TiffImages v0.11.3
  [06e1c1a7] + TiledIteration v0.5.0
  [3bb67fe8] + TranscodingStreams v0.11.3
  [3a884ed6] + UnPack v1.0.2
  [3d5dd08c] + VectorizationBase v0.21.71
  [e3aaa7dc] + WebP v0.1.3
  [efce3f68] + WoodburyMatrices v1.0.0
  [f5851436] + FFTW_jll v3.3.10+3
  [61579ee1] + Ghostscript_jll v9.55.0+4
  [59f7168a] + Giflib_jll v5.2.3+0
  [c73af94c] + ImageMagick_jll v7.1.1+1
  [905a6f67] + Imath_jll v3.1.11+0
  [1d5cc7b8] + IntelOpenMP_jll v2025.0.4+0
  [aacddb02] + JpegTurbo_jll v3.1.1+0
  [88015f11] + LERC_jll v3.0.0+1
  [d4300ac3] + Libgcrypt_jll v1.11.0+0
  [7e76a0d4] + Libglvnd_jll v1.7.0+0
  [7add5ba3] + Libgpg_error_jll v1.51.1+0
  [94ce4f54] + Libiconv_jll v1.18.0+0
  [89763e89] + Libtiff_jll v4.4.0+0
  [d3a379c0] + LittleCMS_jll v2.12.0+0
  [856f044c] + MKL_jll v2025.0.1+1
  [18a262bb] + OpenEXR_jll v3.2.4+0
  [643b3616] + OpenJpeg_jll v2.4.0+0
  [efe28fd5] + OpenSpecFun_jll v0.5.6+0
  [02c8fc9c] + XML2_jll v2.13.6+1
  [aed1982a] + XSLT_jll v1.1.42+0
  [4f6342f7] + Xorg_libX11_jll v1.8.6+3
  [0c0b7dd1] + Xorg_libXau_jll v1.0.12+0
  [a3789734] + Xorg_libXdmcp_jll v1.1.5+0
  [1082639a] + Xorg_libXext_jll v1.3.6+3
  [14d82f49] + Xorg_libpthread_stubs_jll v0.1.2+0
  [c7cfdc94] + Xorg_libxcb_jll v1.17.0+3
  [c5fb5394] + Xorg_xtrans_jll v1.5.1+0
  [3161d3a3] + Zstd_jll v1.5.7+1
  [b53b4c65] + libpng_jll v1.6.47+0
  [075b6546] + libsixel_jll v1.10.5+0
  [c5f90fcd] + libwebp_jll v1.4.0+0
  [1317d2d5] + oneTBB_jll v2022.0.0+0
  [0dad84c5] + ArgTools
  [56f22d72] + Artifacts
  [2a0f44e3] + Base64
  [ade2ca70] + Dates
  [8ba89e20] + Distributed
  [f43a241f] + Downloads
  [7b1f6079] + FileWatching
  [9fa8497b] + Future
  [b77e0a4c] + InteractiveUtils
  [4af54fe1] + LazyArtifacts
  [b27032c2] + LibCURL
  [76f85450] + LibGit2
  [8f399da3] + Libdl
  [37e2e46d] + LinearAlgebra
  [56ddb016] + Logging
  [d6f4376e] + Markdown
  [a63ad114] + Mmap
  [ca575930] + NetworkOptions
  [44cfe95a] + Pkg
  [de0858da] + Printf
  [3fa0cd96] + REPL
  [9a3f8284] + Random
  [ea8e919c] + SHA
  [9e88b42a] + Serialization
  [1a1011a3] + SharedArrays
  [6462fe0b] + Sockets
  [2f01184e] + SparseArrays
  [10745b16] + Statistics
  [4607b0f0] + SuiteSparse
  [fa267f1f] + TOML
  [a4e569a6] + Tar
  [8dfed614] + Test
  [cf7118a7] + UUIDs
  [4ec0a83e] + Unicode
  [e66e0078] + CompilerSupportLibraries_jll
  [deac9b47] + LibCURL_jll
  [29816b5a] + LibSSH2_jll
  [c8ffd9c3] + MbedTLS_jll
  [14a3606d] + MozillaCACerts_jll
  [4536629a] + OpenBLAS_jll
  [05823500] + OpenLibm_jll
  [83775a58] + Zlib_jll
  [8e850b90] + libblastrampoline_jll
  [8e850ede] + nghttp2_jll
  [3f19e933] + p7zip_jll

9.4 s

"https://i.imgur.com/VGPeJ6s.jpg"

# defines a variable called `url`

# whose value is a string (written inside `"`):

url = "https://i.imgur.com/VGPeJ6s.jpg"

👀 Reading hidden code

11.8 μs

"philip.jpg"

philip_file = download(url, "philip.jpg") # download to a local file

👀 Reading hidden code

280 ms

philip = load(philip_file)

👀 Reading hidden code

632 ms

philip

👀 Reading hidden code

13.6 μs

Matrix{RGB{N0f8}} (alias for Array{RGB{Normed{UInt8, 8}}, 2})

typeof(philip)

👀 Reading hidden code

11.1 μs

RGBX(0.9, 0.1, 0.1)

👀 Reading hidden code

24.9 μs

👀 Reading hidden code

223 μs

👀 Reading hidden code

69.6 μs

👀 Reading hidden code

191 μs

Matrix{RGB{N0f8}} (alias for Array{RGB{Normed{UInt8, 8}}, 2})

typeof(philip)

👀 Reading hidden code

10.9 μs

According to Julia / Pluto, the variable philip is an image
Julia always returns output
The output can be displayed in a "rich" way

Arthur C. Clarke:

Any sufficiently advanced technology is indistinguishable from magic.

👀 Reading hidden code

4.3 ms

size(philip)

👀 Reading hidden code

13.4 μs

philip

👀 Reading hidden code

17.3 μs

philip[1:1000, 1:400]

👀 Reading hidden code

518 μs

How big is Philip?

He's pretty big:

👀 Reading hidden code

313 μs

size(philip)

👀 Reading hidden code

11.2 μs

Which number is which?

👀 Reading hidden code

262 μs

philip

👀 Reading hidden code

8.5 μs

So, what is an image?

👀 Reading hidden code

14.3 ms

Matrix{RGB{N0f8}} (alias for Array{RGB{Normed{UInt8, 8}}, 2})

typeof(philip)

👀 Reading hidden code

11.1 μs

It's an Array
The 2 means that it has 2 dimensions (a matrix)

RGBX{Normed{UInt8,8}} is the type of object stored in the array
A Julia object representing a colour
RGB = Red, Green, Blue

👀 Reading hidden code

813 μs

Getting pieces of an image

👀 Reading hidden code

212 μs

begin

(h, w) = size(philip)

head = philip[(h ÷ 2):h, (w ÷ 10): (9w ÷ 10)]

# `÷` is typed as \div <TAB> -- integer division

end

👀 Reading hidden code

4.8 ms

size(head)

👀 Reading hidden code

12.4 μs

size(philip)

👀 Reading hidden code

11.4 μs

Manipulating matrices

An image is just a matrix, so we can manipulate matrices to manipulate the image

👀 Reading hidden code

412 μs

[head head]

👀 Reading hidden code

5.1 ms

👀 Reading hidden code

173 μs

[

head reverse(head, dims=2)

reverse(head, dims=1) reverse(reverse(head, dims=1), dims=2)

]

👀 Reading hidden code

185 ms

Manipulating an image

How can we get inside the image and change it?
There are two possibilities:
- Modify (mutate) numbers inside the array – useful to change a small piece
- Create a new copy of the array – useful to alter everything together

👀 Reading hidden code

672 μs

Painting a piece of an image

Let's paint a corner red
We'll copy the image first so we don't destroy the original

👀 Reading hidden code

405 μs

new_phil = copy(head)

👀 Reading hidden code

2.0 ms

👀 Reading hidden code

241 μs

red = RGB(1, 0, 0)

👀 Reading hidden code

13.4 μs

for i in 1:100

for j in 1:300

new_phil[i, j] = red

end

👀 Reading hidden code

90.6 μs

Note that for loops do not return anything (or, rather, they return nothing)

👀 Reading hidden code

265 μs

new_phil

👀 Reading hidden code

8.6 μs

Element-wise operations: "Broadcasting"

Julia provides powerful technology for operating element by element: broadcasting
Adding "." applies an operation element by element

👀 Reading hidden code

465 μs

begin

new_phil2 = copy(new_phil)

new_phil2[100:200, 1:100] .= RGB(0, 1, 0)

new_phil2

end

👀 Reading hidden code

983 μs

👀 Reading hidden code

209 μs

new_phil2

👀 Reading hidden code

8.7 μs

Modifying the whole image at once

We can use the same trick to modify the whole image at once
Let's redify the image
We define a function that turns a colour into just its red component

👀 Reading hidden code

492 μs

redify (generic function with 1 method)

function redify(c)

return RGB(c.r, 0, 0)

end

👀 Reading hidden code

418 μs

begin

color = RGB(0.9, 0.7, 0.2)

[color, redify(color)]

end

👀 Reading hidden code

43.5 μs

👀 Reading hidden code

168 μs

redify.(philip)

👀 Reading hidden code

113 ms

Transforming an image

The main goal of this week will be to transfrom images in more interesting ways
First let's decimate poor Phil

👀 Reading hidden code

23.1 ms

poor_phil = decimate(head, 5)

👀 Reading hidden code

377 μs

👀 Reading hidden code

185 μs

Experiments come alive with interaction

We start to get a feel for things when we can experiment!

👀 Reading hidden code

363 μs

begin

Pkg.add("PlutoUI")

using PlutoUI

end

👀 Reading hidden code

   Resolving package versions...
    Updating `/tmp/jl_4mrqNz/Project.toml`
  [7f904dfe] + PlutoUI v0.7.23
    Updating `/tmp/jl_4mrqNz/Manifest.toml`
  [6e696c72] + AbstractPlutoDingetjes v1.3.2
  [47d2ed2b] + Hyperscript v0.0.4
  [ac1192a8] + HypertextLiteral v0.9.5
  [b5f81e59] + IOCapture v0.2.5
  [682c06a0] + JSON v0.21.4
  [69de0a69] + Parsers v2.8.1
  [7f904dfe] + PlutoUI v0.7.23
  [410a4b4d] + Tricks v0.1.10

4.0 s

👀 Reading hidden code

193 μs

@bind repeat_count Slider(1:10, show_value=true)

👀 Reading hidden code

238 ms

repeat(poor_phil, repeat_count, repeat_count)

👀 Reading hidden code

250 μs

Summary

Images are readily-accessible data about the world
We want to process them to extract information
Relatively simple mathematical operations can transform images in useful ways

👀 Reading hidden code

414 μs

👀 Reading hidden code

288 μs

expand (generic function with 2 methods)

👀 Reading hidden code

671 μs

extract_red (generic function with 1 method)

👀 Reading hidden code

389 μs

decimate (generic function with 2 methods)

👀 Reading hidden code

726 μs

Appendix

👀 Reading hidden code

173 μs

Package environment

👀 Reading hidden code

194 μs

Camera input

👀 Reading hidden code

181 μs

camera_input (generic function with 1 method)

👀 Reading hidden code

1.4 ms

process_raw_camera_data (generic function with 1 method)

function process_raw_camera_data(raw_camera_data)

# the raw image data is a long byte array, we need to transform it into something

# more "Julian" - something with more _structure_.

# The encoding of the raw byte stream is:

# every 4 bytes is a single pixel

# every pixel has 4 values: Red, Green, Blue, Alpha

# (we ignore alpha for this notebook)

# So to get the red values for each pixel, we take every 4th value, starting at

# the 1st:

reds_flat = UInt8.(raw_camera_data["data"][1:4:end])

greens_flat = UInt8.(raw_camera_data["data"][2:4:end])

blues_flat = UInt8.(raw_camera_data["data"][3:4:end])

# but these are still 1-dimensional arrays, nicknamed 'flat' arrays

# We will 'reshape' this into 2D arrays:

width = raw_camera_data["width"]

height = raw_camera_data["height"]

# shuffle and flip to get it in the right shape

reds = reshape(reds_flat, (width, height))' / 255.0

greens = reshape(greens_flat, (width, height))' / 255.0

blues = reshape(blues_flat, (width, height))' / 255.0

# we have our 2D array for each color

# Let's create a single 2D array, where each value contains the R, G and B value of

# that pixel

RGB.(reds, greens, blues)

end

👀 Reading hidden code

1.4 ms

In the cloud (experimental)

On your computer

Frontmatter

Preview

Welcome to 18.S191 – Fall 2020!

Introduction to Computational Thinking for Real-World Problems

https://github.com/mitmath/18S191

Alan Edelman, David P. Sanders, Grant Sanderson, James Schloss

& Philip the Corgi

Class outline

Data and computation

Tools

Module 1: Images

Data takes many forms

Capture your own image!

What is an image?

What is an image, though?

How can we store an image in the computer?

If in doubt: Ask Julia!

How big is Philip?

So, what is an image?

Getting pieces of an image

Manipulating matrices

Manipulating an image

Painting a piece of an image

Element-wise operations: "Broadcasting"

Modifying the whole image at once

Transforming an image

Experiments come alive with interaction

Summary

Appendix

Package environment

Camera input